from typing import List


# 方法一： 模拟 区间 相交的情况
class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        # 按 左端点 大小排序
        nums.sort()

        left = nums[0][0]
        right = nums[0][1]
        # 初始化 ans为第一段区间的长度
        ans = right - left + 1
        for num in nums[1:]:
            # 模拟每段区间 更新区间的长度 和 ans
            # 两端区间相交
            if left <= num[0] <= right:
                # 情况1： 当前区间 被 包在 left 和 right 里，不用更新ans
                if num[1] <= right:
                    continue
                # 情况二： 当前区间 的 右端点 大于 right，区间更新right到num[1]
                else:
                    ans += num[1] - right
                    right = num[1]
            # 情况三： 两端区间 不相交
            if num[0] > right:
                ans += num[1] - num[0] + 1
                left = num[0]
                right = num[1]

        return ans

# 方法二： 差分
# 初始化差分数组：因为题目给定的区间范围是有限的，假设所有区间的端点值都在一个合理的范围内（例如本题中，端点值最大为 100），可以创建一个长度为 max_end + 1 的差分数组 diff，初始值都为 0。
# 区间修改：遍历每个区间 [start, end]，在差分数组的 start 位置加 1，表示从该位置开始有一个区间覆盖；在 end + 1 位置减 1，表示该区间在 end 位置结束覆盖。
# 前缀和还原：对差分数组进行前缀和运算，得到原数组，原数组中值大于 0 的位置表示被区间覆盖。
# 统计覆盖点数：遍历前缀和数组，统计值大于 0 的位置的数量，即为最终结果。

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        # 找到所有区间端点的最大值
        max_end = max(end for _, end in nums)
        # 初始化差分数组
        diff = [0] * (max_end + 2)
        # 区间修改
        for start, end in nums:
            diff[start] += 1
            diff[end + 1] -= 1
        # 前缀和还原
        pre = [0] * (max_end + 2)
        pre[0] = diff[0]
        for i in range(1, max_end + 2):
            pre[i] = pre[i - 1] + diff[i]

        # 统计 大于 0 的个数
        return sum(s > 0 for s in pre)
